package com.kehao.leetcode.hard.tree_graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class CountSmallerSolution {
    //直接采用for循环 会超时 时间复杂度必须小于O（n^2）
    public List<Integer> countSmaller1(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i+1; j < nums.length; j++) {
                if(nums[j]<nums[i]){
                    count++;
                }
            }
            result.add(count);
        }
        return result;
    }

    //还是会超时 理论上应该已经有O（nlogn）了 可能是构建的二叉树不是平衡二叉树 导致最坏情况依然是O（n^2）
    private static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public int count = 0;
        public int leftCount = 0;
        TreeNode(int val){
            this.val = val;
        }
    }

    public List<Integer> countSmaller2(int[] nums) {
        TreeNode head = new TreeNode(nums[nums.length-1]);
        Integer[] array = new Integer[nums.length];
        array[nums.length-1] = 0;
        for (int i = nums.length-2 ; i >=0; i--) {
            TreeNode p = new TreeNode(nums[i]);
            buildTree(head,p);
            array[i] = p.count;
        }
        return Arrays.asList(array);
    }

    private void buildTree(TreeNode head,TreeNode p){
        if(p.val<=head.val){
            head.leftCount++;
            if(head.left!=null){
                buildTree(head.left,p);
            }else {
                head.left = p;
            }
        }else {
            p.count++;
            p.count += head.leftCount;
            if(head.right!=null){
                buildTree(head.right,p);
            }else {
                head.right = p;
            }
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        Integer[] resultArray = new Integer[nums.length];
        ArrayList<Integer> arrayList = new ArrayList<>();
        resultArray[nums.length-1] = 0;
        arrayList.add(nums[nums.length-1]);
        for (int i = nums.length-2; i>=0 ; i--) {
            int l = 0, r = arrayList.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (arrayList.get(mid) < nums[i]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            resultArray[i] = l;
            arrayList.add(l,nums[i]);
        }
        return Arrays.asList(resultArray);
    }


    @Test
    public void test01(){
       int[] nums = {5,2,6,1};
       countSmaller(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test02(){
        int[] nums = {-1};
        countSmaller(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test03(){
        int[] nums = {-1,-1};
        countSmaller(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test04(){
        int[] nums = {1,0,2};
        countSmaller(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test05(){
        int[] nums = {2,0,1};
        countSmaller(nums).forEach(i-> System.out.print(i+" "));
    }
}
